资源分配——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

将有限的资源分配给多个需求方，目标是最大化资源利用率 / 收益或最小化资源消耗，每一步选择对当前资源最 “高效” 的分配方式。

本教程以多个资源分配贪心算法案例场景为例，让大家彻底理解以 “局部最优” 推导 “全局最优” 的核心逻辑，并掌握部分背包、最优装载问题的原理及代码实现。

部分背包问题：背包有容量限制，物品可分割，选择单位重量价值最高的物品优先装入，最终总价值最大。实际场景：物流货车装货（按单位体积利润优先装）、资金分配（按单位资金收益率优先投资）。
最优装载问题：船有载重限制，物品不可分割，选择重量最轻的物品优先装，最大化装载数量。实际场景：飞机乘客行李装载（优先装轻行李，提升装载件数）、仓库堆货（按体积小优先堆，提升堆货数量）。

教程目录导航

▼

排序问题
- 一、部分背包问题
- 二、最优装载问题

一、部分背包问题

问题描述：

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N≤100) 堆金币，第 i 堆金币的总重量和总价值分别是 m_i,v_i(1≤m_i ,v_i≤100)。阿里巴巴有一个承重量为 T(T≤1000) 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？
输入格式:
1. 第一行两个整数 N,T。
2. 接下来 N 行，每行两个整数 m_i,v_i。
输出格式:
1. 一个实数表示答案，输出两位小数

算法解析：

性价比 = 价值 / 重量。
n堆金币按性价比排序
依次遍历，如果背包中剩余可以拿的重量大于等于这堆金币的重量，就全拿，否则直接装满。


#include <iostream>
#include <vector>

using namespace std;

// 金币结构体：重量、价值
struct Gold {
    double weight;//重量
    double value;//价值

    // 性价比(单位重量价值)
    double valuePerWeight() const {
        return value / weight;
    }
};

// 按性价比降序排序
bool compareGold(const Gold& a, const Gold& b) {
    return a.valuePerWeight() > b.valuePerWeight();
}

// 部分背包求解：capacity-背包容量，golds-金币列表，返回最大总价值
double fractionalKnapsack(double capacity, vector<Gold>& golds) {
    sort(golds.begin(), golds.end(), compareGold);
    double totalValue = 0.0;
    double currentWeight = 0.0;

    for (auto& item : golds) {
        // 能装下整个物品
        if (currentWeight + item.weight <= capacity) {
            currentWeight += item.weight;
            totalValue += item.value;
        } else {
            // 装剩余部分
            double remain = capacity - currentWeight;
            totalValue += item.valuePerWeight() * remain;
            break; // 背包已满
        }
    }
    return totalValue;
}

int main() {
    // 测试：3堆金币，背包容量50
    vector<Gold> golds = {{10, 60}, {20, 100}, {30, 120}};
    double capacity = 50;
    cout << "部分背包最大价值：" << fractionalKnapsack(capacity, golds) << endl;

    return 0;
}

输出结果


部分背包最大价值：240

二、最优装载问题

问题描述：

顺风快递要将物流中心的一批货物从长沙空运到上海。为了尽可能的多装货物，物流中心工作人员已经将货物按照重量和体积进行了分类打包（每包体积相同），总共有N包货物，第 i 包货物的总重量和货物数量分别是m_i,v_i(1≤m_i ,v_i≤100)，运输机的承重量为 T(T≤1000)，但并不一定有办法将货物全部装进去。顺风快递想运走尽可能多的货物。打包好的货物不能分割。请问运输机最多可以运走多少件货物？

算法解析：

单个重量 = 重量 / 数量
从单个重量最轻货物开始依次选取，直到加入下一包货物超出运输机的载重限制；
统计装载数量，得到最优解。


#include <iostream>
#include <vector>

using namespace std;

// 定义货物包结构体
struct Wrap {
    int id;     // 包编号
    double weight; // 货物重量
    double qty; // 货物数量
    // 构造函数，方便初始化
    Wrap(int i, double w, double q) : id(i), weight(w), qty(q) {}

    // 单个重量
    double unitWeight() const {
        return weight / qty;
    }
};

// 排序比较函数：按重量升序排序（轻的在前）
bool compareWrap(const Wrap &a, const Wrap &b) {
    return a.unitWeight() < b.unitWeight();
}

// 最优装载问题
// 参数：wraps-货物包结构体数组，maxCapacity最大载重
void optimalLoading(vector<Wrap> wraps, int maxCapacity, vector<int>& selectedIds, int& totalWeight, int& count) {
    // 步骤1：按重量升序排序
    sort(wraps.begin(), wraps.end(), compareWrap);

    // 步骤2：依次选取货物物品，保留包编号
    for (const Wrap &wrap : wraps) {
        if (totalWeight + wrap.weight <= maxCapacity) {
            selectedIds.push_back(wrap.id);
            totalWeight += wrap.weight;
            count+=wrap.qty;
        } else {
            break;// 背包已满
        }
    }
}

int main() {
    // 测试：5包货物，载重量100
    vector<Wrap> wraps = {{1, 50, 60}, {2, 50, 70}, {3, 50, 80}, {4, 30, 80}, {5, 20, 70}};
    double maxCapacity = 100;// 载重量
    vector<int> selectedIds;// 已载包编号
    int totalWeight = 0;// 已载货物重量
    int count = 0;// 已载货物数量

    optimalLoading(wraps, maxCapacity, selectedIds, totalWeight, count);

    cout << "已载货物重量：" << totalWeight << endl;
    cout << "已载货物数量：" << count << endl;
    cout << "已载包编号：";
    for(int id : selectedIds)
    {
        cout << id << " ";
    }

    return 0;
}

输出结果


已载货物重量：100
已载货物数量：230
已载包编号：5 4 3

返回顶部